Low-density parity-check (LDPC) codes have recently been the subject of increased research interest for their enhanced performance on additive white Gaussian noise (AWGN) channels. As described by Shannon's Channel Coding Theorem, the best performance is achieved when using a code consisting off very long codewords. In practice, codeword size is limited in the interest of reducing complexity, buffering, and delays. LDPC codes are block codes, as opposed to trellis codes that are built on convolutional codes. LDPC codes constitute a large family of codes including turbo codes. Block codewords are generated by multiplying (modulo 2) binary information words with a binary matrix generator. LDPC codes uses a check parity matrix H, which is used for decoding. The term low density derives from the characteristic that the check parity matrix has a very low density of non-zero values, making it a relatively low complexity decoder while retaining good error protection properties.
The parity check matrix H measures (N−K)×N, wherein N is number of elements in a codeword and K is the number of information elements in the codeword. The matrix H is also termed the LDPC mother code. For the specific example of a binary alphabet, N is the number of bits in the codeword and K is the number of information bits contained in the codeword for transmission over a wireless or a wired communication network or system. The number of information elements is therefore less than the number of codeword elements, so K<N. FIGS. 1A and 1B graphically describe an LDPC code. The parity check matrix 20 of FIG. 1A is an example of a commonly used 512×4608 matrix, wherein each matrix column 22 corresponds to a codeword element (variable node of FIG. 1B) and each matrix row 24 corresponds to a parity check equation (check node of FIG. 1B). If each column 22 of the matrix H includes exactly the same number m of non-zero elements, and each row 24 of the matrix H includes exactly the same number k of non-zero elements, the matrix 20 represents what is termed a regular LDPC code. If the code allows for non-uniform counts of non-zero elements among the columns 22 and/or rows 24, it is termed an irregular LDPC code.
Irregular LDPC codes have been shown to significantly outperform regular LDPC codes, which has generated renewed interest in this coding system since its inception decades ago. The bipartite graph of FIG. 1B illustrates that each codeword element (variable nodes 26) is connected only to parity check equations (check nodes 28) and not directly to other codeword elements (and vice versa). Each connection, termed a variable edge 30 or a check edge 31 (each edge represented by a line in FIG. 1B), connects a variable node 26 to a check node 28 and represents a non-zero element in the parity check matrix H. The number of variable edges 30 connected to a particular variable node 26 is termed its degree, and the number of variable degrees 32 are shown corresponding to the number of variable edges 30 emanating from each variable node 26. Similarly, the number of check edges 31 connected to a particular check node 28 is termed its degree, and the number of check degrees 34 are shown corresponding to the number of check edges 31 emanating from each check node 31. Since the degree 32, 34 represents non-zero elements of the matrix H, the bipartite graph of FIG. 1B represents an irregular LDPC code matrix. The following discussion is directed toward irregular LDPC codes since they are more complex and potentially more useful, but may also be applied to regular LDPC codes with normal skill in the art.
Irregular codes can be designed for many different symmetric channels via density evolution and genetic hill-climbing algorithms (i.e., Differential Evolution) by adjusting variable edge polynomial λ(x) and check edge polynomial ρ(x), defined as:
      λ    ⁡          (      x      )        =                    ∑                  i          =          2                          d          l                    ⁢                        λ          i                ⁢                  x                      i            -            1                          ⁢                                  ⁢        and        ⁢                                  ⁢                  ρ          ⁡                      (            x            )                                =                  ∑                  i          =          2                          d          r                    ⁢                        ρ          i                ⁢                  x                      i            -            1                              where {λ2, λ3, . . . λdl} and {ρ2, ρ3, . . . ρdr} are the edges distributions indicating the fraction of edges 30, 31 connected to variable and check nodes of degrees {2, 3, . . . dl} and {2, 3, . . . dr}, respectively, out of the total number of edges. The edge distributions determine the asymptotic performance of the code ensemble, the code rate of the ensemble, and any code realizations derived from the distributions. The coding rate R for an LDPC code is R=K/(N−P), wherein P is the number of punctured elements, detailed below. Preferably, a transmission can be sent using a plurality of adaptive coding rates.
FIG. 2A is a prior art logical block diagram showing operation of a discrete communication system 36A using an LDPC coding scheme of multiple coding rates for its error control. An information source 38 outputs a K dimensional sequence of information bits s into a transmitter 39A, the transmitter including at least an encoder 40A, a modulation block 42, and storage 35A, 37A. An LDPC encoder 40 encodes the sequence s into an N dimensional codeword t by accessing a stored LDPC mothercode definition 37A and one of several stored puncture sequences 35A, one puncture sequence corresponding to one code rate. The codeword t is broken up into sub-vectors, which are then modulated and up-converted at a modulation block 42 and transmitted as a vector x of the sub-vectors over one or more channels 44. Additive white Gaussian noise n is added at the channel and/or from system hardware, so that the vector y=x+n is input into a receiver 45A. The receiver 45A includes at least a demodulation block 46, a decoder 48A, and memory storage for the same LDPC mother code 37A and the same puncture sequences 35A used by the transmitter 39A. Since x and n are uncorrelated and the modulation is memoryless, the received vector y can be demodulated symbol-by-symbol at a demodulating block 46, producing a hard decision vector {circumflex over (t)} on the received information vector t. Probabilities of the decision being correct are also calculated at the demodulation block 46, and all this is input into an LDPC decoder 48A that iteratively decodes the entire received code block and outputs a decoded information vector ŝ to an information sink 50.
The two prior art LDPC coding systems known to the inventor require significant non-volatile memory for each coding rate for a single mother code. In a first prior art approach, a different LDPC code is designated for each coding rate and channel (i.e., different code realizations from different λ(x) and ρ(x) corresponding to the desired code rates). This approach uses one LDPC code for each coding rate, and may increase substantially when the set of code rates is large and/or when code words are long. The storage requirements can render this approach prohibitive for adaptive coding and modulation schemes operating in slowly varying channels.
The second known prior art approach is to take a single LDPC code and puncture codeword elements using multiple puncturing sequences chosen at random using puncturing probabilities. This approach requires storage of multiple puncturing sequences, one for each code rate, which may become prohibitive for a large set of coding rates and/or long codeword lengths. FIG. 3 illustrates the storage requirements of such a system. To support all possible code rates of a punctured LDPC mother code, the system would need to store N−K different puncture sequences 52. Each horizontal line represents a unique stored puncture sequence 52, indexed as S1, S2, S3, . . . SN—K, that applies to a specific coding rate R1, R2, R3, . . . RN−K. The total memory requirement for such a system is
      ∑          i      =      1              N      -      K        ⁢  iuncompressed memory elements.
Besides substantial amounts of memory required to store prior art puncturing sequences for various coding rates, the determination of the puncturing sequences is itself computationally intensive. Like the coding systems themselves, the prior art reveals at least two distinct methods for designing a puncture sequence. The first method is based on linear programming to determine puncturing probabilities that maximize the puncturing fraction:
      p          (      0      )        =            ∑              j        =        2                    d        l              ⁢                  λ        j        ′            ⁢              π        j                  (          0          )                    for a given signal to noise ratio (SNR, or bit/symbol energy to noise power spectral density Eb/N0) threshold, wherein λ′j represents the fraction of variable nodes 26 of degree j. The other prior art approach to puncture sequence design is based on differential evaluation based on Density Evolution, which is somewhat more complex than the linear programming method described immediately above with near identical results. Each of these approaches for designing the puncture sequences are very computationally expensive, and their resulting sequences themselves require so much storage as to be potentially prohibitive for an adaptive coding system.
Thus, each of the known prior art approaches require substantial amounts of storage to implement a wide variety of code rates. It is anticipated that neither of the prior art approaches are suitable for future communication systems that employ adaptive coding and implement a wide range of coding rates. Additionally, each of the two noted prior art approaches in designing puncture sequences are computationally intensive. What is needed in the art is a more elegant set of puncture codes that will not require so much storage as to make their use prohibitive in the adaptive coding rate communications systems that represent what may be a large portion of future communications. Ideally, such an elegant set of puncture codes would also submit to a more straightforward method of determining them, so that more sets of such codes could be developed and optimized for different applications to close further on the theoretical Shannon capacity limit.